package codingPractice.huawei;


import java.util.Arrays;
import java.util.Scanner;

/**
 * 圣诞节到了，豆豆的妈妈准备了很多圣诞礼盒，礼盒大小不同，豆豆在玩堆盒子的游戏，妈妈问豆豆，怎么堆盒子使得堆出的高度最高，
 * 每个礼盒的大小由长、宽、高表示，堆盒子的时候要求下面的盒子长、宽、高都必须大于上面的盒子，不包含等于。
 * 请你帮助豆豆一起堆出最高的一堆礼盒，高度为堆出的礼盒的所有高度的总和。
 *
 * 输入
 * 输入的第一行是礼盒的个数N，接下来输入N行，每行表示每个礼盒的长、宽、高。礼盒的数量不超过1000个，每个盒子的长、宽、高取值范围为1~10。
 *
 * 输出
 * 输出一行，输出能堆出盒子的最高高度
 */
public class ChristmasGift {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNextInt()) {
            int N = sc.nextInt();
            int[][] vol = new int[N][3];
            for(int i=0;i<N;i++) {
                vol[i][0] = sc.nextInt();
                vol[i][1] = sc.nextInt();
                vol[i][2] = sc.nextInt();
            }

            int result = getMaxStackHeight(vol);
            System.out.println(result);
        }
    }

    public static int getMaxStackHeight(int[][] boxes) {
        int n = boxes.length;

        Box[] boxArr = new Box[n];
        for(int i=0;i<n;i++) {
            boxArr[i] = new Box(boxes[i][0], boxes[i][1], boxes[i][2]);
        }

        Arrays.sort(boxArr);

        //动态规划数组，记录以每个盒子为最上层时的最大堆叠高度
        int[] maxHeight = new int[n];

        //初始化，每个盒子作为最上层时的高度为它自身的高度
        for(int i=0;i<n;i++) {
            maxHeight[i] = boxArr[i].height;
        }

        //动态规划，计算最大堆叠的高度
        for(int i=1;i<n;i++) {
            for(int j=0;j<i;j++) {
                if (boxArr[i].length > boxArr[j].length &&
                    boxArr[i].width > boxArr[j].width &&
                    boxArr[i].height > boxArr[j].height) {
                    maxHeight[i] = Math.max(maxHeight[i], maxHeight[j] + boxArr[i].height);
                }
            }
        }

        //找到最大堆叠高度
        int maxStackHeight = 0;
        for(int height : maxHeight) {
            maxStackHeight = Math.max(maxStackHeight, height);
        }

        return maxStackHeight;
    }
}

class Box implements Comparable<Box> {
    int length, width, height;

    public Box (int length, int width, int height) {
        this.length = length;
        this.width = width;
        this.height = height;
    }

    @Override
    public int compareTo(Box o) {
        if(this.length != o.length) {
            return this.length - o.length;
        } else {
            return this.width - o.width;
        }
    }
}
